#include"Heap.h"
void test01() {
	Heap hp;
	HPInit(&hp);
	HPPush(&hp,3);
	HPPush(&hp,6);
	HPPush(&hp,2);
	HPPush(&hp,9);
	HPPush(&hp,20);
	HPPush(&hp,13);
	HPDestroy(&hp);
}
void test02() {
	Heap hp;
	HPInit(&hp); 
	HPPush(&hp, 3);
	HPPush(&hp, 6);
	HPPush(&hp, 2);
	HPPush(&hp, 9);
	HPPush(&hp, 20);
	HPPush(&hp, 13);
	for (size_t i = 0; i < 6; i++)
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}
	printf("\n");
	HPDestroy(&hp);
}

void HeapSort1(int* arr,int size) {
	for (int i = 0; i < size; i++) {
		AdJustUp(arr, i);
	}//建堆复杂度O(N*logN)
	/*for (size_t i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");*/
	int end = size - 1;
	while (end >= 0) {
		Swap(&arr[end], &arr[0]);
		AdJustDown(arr, 0, end);
		end--;
	}
}//堆排序——小堆降序（向上调整算法建堆）时间复杂度O(N*logN)


void HeapSort2(int* arr, int size) {
	for (int i = (size - 1 - 1)/2; i >= 0; i--) {
		AdJustDown(arr, i, size);
	}//建堆时间复杂度 O(N)
	for (size_t i = 0; i < size; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	
	int end = size - 1;
	while (end >= 0) {
		Swap(&arr[end], &arr[0]);
		AdJustDown(arr, 0, end);
		end--;
	}
}//堆排序——小堆降序（向下调整算法建堆）//时间复杂度O(N*logN)

void test03() {
	int arr[] = { 2,4,1,4,54,2,46,46,23,4324,6 };
	HeapSort1(arr, sizeof(arr) / sizeof(arr[0]));
	for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
void test04(){
	int arr[] = { 2,4,1,4,54,2,46,46,23,4324,6 };
	HeapSort2(arr, sizeof(arr) / sizeof(arr[0]));
	for (size_t i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
int main() {
	//test01();
	//test02();
	//test03();
	test04();
	return 0;
}